package class_0927FibHeap;

public class FibHeap<V> {
    public static class Node<V>{
        int key;
        V value;
        Node<V> left;
        Node<V> right;
        Node<V> p;
        int degree;
        boolean mark;
        public Node(int key, V value){
            this.key = key;
            this.value = value;
        }
    }
    private Node<V> min;//Fib堆的指针
    private int size;
    public static <V> FibHeap<V> make_fib_heap(){
        FibHeap<V> heap = new FibHeap<V>();
        heap.min = null;
        heap.size = 0;
        return heap;
    }

    public void insert(int key, V value){
        insert(new Node<V>(key , value));
    }


    private void insert(Node<V> node){
        node.degree = 0;
        node. p = node.left = node.right = node;
        node.mark = false;
        if(min == null){
            min = node;
        }
        else{
            //连接节点
            node.right = min.right;
            min.right.left = node;
            min.right = node;
            node.left = min;
            if(node.key < min.key){
                min = node;
            }
        }
        size++;
    }

    public FibHeap<V> union(FibHeap<V> other) {
        FibHeap<V> newHeap = new FibHeap<V>();

        // 合并两个堆的最小节点
        if (this.min != null) {
            newHeap.min = this.min;
        }
        if (other.min != null) {
            if (newHeap.min == null) {
                newHeap.min = other.min;
            } else {
                // 连接两个堆的最小节点
                Node<V> thisRight = this.min.right;
                Node<V> otherRight = other.min.right;
                this.min.right = otherRight;
                other.min.right = thisRight;
                thisRight.left = other.min;
                otherRight.left = this.min;

                // 更新最小节点
                if (other.min.key < this.min.key) {
                    newHeap.min = other.min;
                }
            }
        } else {
            newHeap.min = other.min;
        }

        newHeap.size = this.size + other.size;
        return newHeap;
    }

}
